import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/22 20:47
 * @description 倒序 Rabin Karp算法
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();;
        solution.subStrHash("leetcode", 7, 20, 2, 0);
    }
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        int mul = 1;
        int n = s.length();
        // 第一个符合要求子串的起始下标
        int pos = -1;
        // 子串哈希值
        long h = 0;
        // 预处理计算最后一个子串的哈希值和 power^k mod modulo
        char[] S = s.toCharArray();
        for (int i = n - 1; i >= n - k; --i) {
            h = (h * power + (S[i] - 'a' + 1)) % modulo;
            if (i != n - k) {
                mul = (int) ((long) mul * power % modulo);
            }
        }
        if (h == hashValue) {
            pos = n - k;
        }
        // 向前计算哈希值并尝试更新下标
        for (int i = n - k - 1; i >= 0; --i) {
            h = ((h - (long)(S[i+k] - 'a' + 1) * mul % modulo + modulo) * power + (S[i] - 'a' + 1)) % modulo;
            if (h == hashValue) {
                pos = i;
            }
        }
        return s.substring(pos, pos + k);

    }
}
